package com.mlh.binarytree;

//判断是否为二叉平衡树
public class IsBalanced {

    public static boolean balanced(TreeNode root){
        return process(root)[0]==1?true:false;
    }

    //定义一个数组  为所需信息数组
    //arr[0]  1表示为符合平衡二叉树  0表示不符合
    //arr[1]  表示树的高度
    public static int[] process(TreeNode node){
        if(node ==null){
            return new int[]{1,0};
        }
        //判断左右子树是否平衡，且返回最大高度
        int[] left=process(node.left);
        int[] right=process(node.right);
        if(left[0]==0||right[0]==0){
            return new int[]{0,-1};
        }

        //获取子树中最大高度，进而算出自身的最大高度
        int height=Math.max(left[1],right[1])+1;
        //res 表示该树的左右子树高度差是否|左子树高度-右子树高度|<2
        int res=Math.abs(left[1]-right[1])<2?1:0;
        //isBalance表示该树的是否符合平衡二叉树
        int isBalance=left[0]*right[0]*res;
        //把该树是否为平衡二叉树 和 高度返回出去
        return new int[]{isBalance,height};
    }

    //力扣 执行时间更快
    public boolean method2(TreeNode root) {
        return recursion(root) != -1;
    }
    //他这里将是否为平衡二叉子树和二叉树的高度信息合成一个变量
    int recursion(TreeNode root) {
        if (root == null) return 0;
        int left = recursion(root.left);
        int right = recursion(root.right);
        if (left == -1 || right == -1) return -1;
        //树的左右子树高度差是否<2
        if (Math.abs(left - right) > 1) return -1;
        return Math.max(left, right) + 1;
    }
}
